1. The Field of the Invention
The present invention relates to data mapping using a sparse lookup table in a manner that approximates linear interpolation. More specifically, the present invention relates to mapping of data by quantizing data samples and accessing a lookup table such that the average of the output data for a neighborhood of samples converges to a result that is comparable with or approximates the result that would have been obtained using linear interpolation.
2. The Prior State of the Art
Printing an image using a computer printer or another image forming system often involves processing color image data by converting the image data from a first color space to a second color space. For example, image data is often stored or received by a computer in a red, green, blue (xe2x80x9cRGBxe2x80x9d) format, while many computer printers utilize a cyan, magenta, yellow (xe2x80x9cCMYxe2x80x9d) or cyan, magenta, yellow, black (xe2x80x9cCMYKxe2x80x9d) format. Such formats are examples of image data that can exist in any number of color spaces. The process of converting color image data from a first color space to a second color space represents but one example of a general mathematical problem of evaluating a multivariable function given specific values of the input variables.
There exist several techniques for converting image data from a first color space to a second color space. In practice, image data typically includes a plurality of samples, each being represented by multiple values associated with the different color components in a color space. For example, each sample of RGB data includes a red component, a green component, and a blue component. One approach for converting such RGB image data to CMY data uses a set of three equations defining C, M and Y as linear functions of R, G, and B. Assuming the R, G, and B components of the image data are represented by eight bits of data, in which case the intensity of each of the three components has a value between 0 and 255, the linear approach for converting RGB to CMY can be defined as C=255xe2x88x92R; M=255xe2x88x92G; Y=255xe2x88x92B. This approach is relatively computationally efficient, since each sample can be converted by performing only three calculations, none of which is a division operation. However, in practice, this direct approach introduces unacceptable errors because the available colorants used in image forming systems do not behave in the linear fashion described in the foregoing equations.
A second technique is to obtain a set of higher order polynomials that define CMY(K) as functions of RGB. This analytic method can reduce errors, since it can more closely approximate the actual behavior of specific colorants that are used in image forming systems. However, as the analytic polynomials are taken to higher orders, the number of calculations per sample increases. Moreover, any set of higher order polynomials are adapted only to a specific set of colorants, and any change in the colorants and the associated color conversion functions would require a new set of polynomials.
FIG. 1 graphically illustrates the technique for directly calculating the value of a function, f(x), based on the known value of x. Conceptually, FIG. 1 represents the conversion method that uses a set of higher order polynomials to convert image data from a first color space to a second color space, although FIG. 1 illustrates the problem in only one dimension, whereas RGB to CMY(K) conversion requires a three-dimensional solution. In FIG. 1, the known value of x can be used to directly calculate the value of f(x) (shown at 10) to any desired degree of accuracy that is limited only by the degree of the polynomial function and by the computing resources dedicated to the process.
The two foregoing techniques for converting image data from a first color space to a second color space involve direct calculation of values in the second color space using functions that are defined with any desire degree of accuracy. Other methods for converting image data from first color space to a second color space involve lookup tables in which the values of CMY(K) as a function of RGB are pre-calculated and stored for use during the conversion process. The lookup table eliminates direct calculation of the color values at runtime, but requires memory to be accessed for each sample. A lookup table used for converting RGB to CMY(K) can be described as having three dimensions, that when fully populated, has 16,777,216 entries (e.g., 256xc3x97256xc3x97256), assuming eight bit values for each of the RGB components of the image data, which also corresponds to the number of colors that can be defined by such image data. As can be readily understood, a fully populated lookup table can require a prohibitive amount of memory. Although a fully populated lookup table can yield results having any desired degree of accuracy, the memory and computational requirements make them impractical in most image forming systems.
These memory and computational requirements can be reduced using a sparsely populated lookup table that includes entries for fewer than all of the possible combinations of RGB values. Empirically, it has been found that the curvature of the color conversion functions can be adequately approximated by using a lookup table having 17 lattice points for each color dimension. This technique requires a lookup table having fewer than 5,000 entries.
FIG. 2A illustrates the conversion function of FIG. 1 having been defined by a series of discrete points 12 that can be used in a lookup table, as opposed to being defined by a continuous curve. FIG. 2B conceptually illustrates a sparsely populated lookup table 20 having three dimensions that can be used to convert image data from a first color space (e.g., RGB) to a second color space (e.g., CMY(K)). Only some of the data points 22 defined in lookup table 20 are illustrated in FIG. 2B for purposes of clarity. In a fully populated lookup table, each possible sample, represented by eight bit values of R, G, and B would map to a single point in a lookup table, which in turn would correspond to a set of CMY(K) values. In the sparse lookup table 20, only a relatively small number of values of R, G and B map directly to a lattice points 22. Those samples that map directly to a lattice point 22 yield the corresponding CMY(K) values associated with the lattice point. The vast majority of RGB values, however, map to a position in the sparsely populated lookup table that does not coincide with a lattice point. In order to evaluate the conversion functions for such samples of image data, a method of approximating the value of the conversion functions is used.
One conventional way of approximating the value of the conversion functions involves truncating specified numbers of bits from the RGB values to obtain index values that map directly to lattice points in the sparsely populated lookup table. For purposes of illustration, the analogous one dimensional truncation technique is illustrated in FIG. 3, in which the value of f(x) is to be approximated based on the known value of x. In FIG. 3 it is assumed that the input data defines x with eight bits of accuracy, while f(x) has been defined at 17 discrete points, each of which corresponds to an entry in a lookup table. Truncation of the eight bit input data by four bits results in quantized input data including the four most significant bits, which can be mapped to one of the lookup table entries as shown by the stairstep pattern 30a. Truncation in this matter effectively results in the values of the input data being rounded down to the next entry of the lookup table. For example, input data having a value of 127 (0111 1111) when truncated indexes the same lookup table entry and yields the same output data as an input value of 96 (0111 0000). Accordingly, the samples are quantized, meaning that the same output value is generated for a range of input values.
In an image forming system, such as a computer printer, the result can be a color artifact known as contour bands, which are same-colored stripes or regions on the rendered image. contour banding can be observed when the number of discrete output values is sufficiently small that the difference between successive values can be perceived by the human eye, which is typically the case for RGB lookup tables having only 17 lattice points in each dimension. Moreover, the maximum error at an individual sample (e.g. one at an edge of a contour band, or 127 in the example of FIG. 3) using this truncation technique is almost as great as the difference in the value of the function at adjacent lattice points. There is also generally an overall error, as can be seen in FIG. 3, in which the average evaluation of f(x) is too low due to the positive slope of f(x).
The maximum error for any sample and the overall error can be reduced by combining the truncation operation with a rounding operation, whereby the truncated values are rounded to the nearest lookup table entry rather than being always rounded down. As a result, the stairstep pattern 30b is shifted to the left as shown in FIG. 3 and the maximum error for any given sample is reduced by approximately a factor of 2, although any contour banding artifacts remain. Either of the foregoing approximation techniques are relatively computationally efficient, in that they involve only truncation and, optionally, rounding, operations and a single lookup table access per sample. The significant drawbacks of this method, however, include noticeable contour bands that can be introduced into the rendered image, errors at individual samples and overall errors.
Linear interpolation rather than truncation or rounding can be used to significantly reduce the local and overall errors that otherwise are associated with the use of sparsely populated lookup tables. FIG. 4 graphically represents conventional one-dimensional linear interpolation, which will be well understood by those skilled in the art. Points A and B represent lattice points or entries in a lookup table and f(A) and f(B) represent the known values of the conversion function at A and B. Linear interpolation assumes that f(x) is linear in the region between points A and B, which assumption enables the approximation of f(x) to be readily calculated. Linear interpolation in one dimension as illustrated in FIG. 4 is relatively straightforward and computationally efficient. However, as the number of dimensions of the conversion function increases to two and particularly three or more variables or dimensions, the complexity of the linear interpolation problem increases exponentially.
Three dimensional linear interpolation, such as that which has been used in association with sparsely populated lookup tables to convert RGB image data to CYM(K) data, involves a significant number of lookup table accesses and calculations per sample. In general, linear interpolation requires the sample to be bounded by a sufficient number of points that allows interpolation to be conducted. In the three dimensional problem, trilinear interpolation can be performed by selecting the eight lattice points that define a cube or a rectangular region that contains the sample. Other three dimensional linear interpolation techniques have been developed, including tetrahedral trilinear interpolation that selects only four points defining a tetrahedron that encloses the sample. However, the tradeoffs for tetrahedral interpolation include identifying which of the multiple available lattice points should be selected as vertices of the tetrahedron that bounds the sample. In any case, trilinear interpolation requires multiple accesses of the lookup table (as many as eight) for each sample and also requires a number of calculations per sample to complete the interpolation process.
In addition to these interpolation techniques, there have been developed other approaches for identifying the converted image data values to be applied to samples using sparsely populated lookup tables. For example, U.S. Pat. No. 5,377,041 to Spaulding, et al. discloses a process of applying a spatial modulation to input color values prior to quantizing the color values. The spatial modulation is disclosed by Spaulding as being local mean-preserving and it introduces variation into the input color values such that successive instances of a specific color value can result in different quantized values.
The foregoing methods for calculating or approximating the value of a function either suffer from computational complexity, frequent access of lookup tables, prohibitive memory requirements, or local or overall errors and associated color artifacts. In view of the foregoing, there is a need for methods and systems for evaluating or approximating the value of a function using a sparsely populated lookup table while avoiding the problems associated with prior art methods.
The present invention relates to approximating the value of a function using a sparsely populated lookup table and known values, or samples, of input data. In one implementation, the invention can be used to perform a color conversion operation on image data in printers or other image forming systems. Rather than performing linear interpolation for samples of the data, the methods of the invention involve a dithered quantization of the samples prior to using the samples as indices to the lookup table. Although the dithered quantization introduces local errors at individual samples, the output data generated for a neighborhood of samples approximates, or converges to, the output data that could be obtained using conventional linear interpolation.
One significant advantage of the methods of the invention is that as few as one lookup table access per sample can be performed because of the quantization of the samples. In contrast, conventional tetrahedral trilinear interpolation requires at least four lookup table accesses for samples that do not coincide with lattice points of the lookup table, while other trilinear interpolation procedures require eight lookup table accesses per sample. Although local errors are introduced by the quantization operations of the invention, the approximation of the output data that could be obtained using conventional linear interpolation is generally acceptable, particularly in environments where the sample density is great enough such that the local errors are imperceptible. For instance, the invention can be practiced in image forming systems, such as printers, in which the pixel density is high enough that the human eye does not readily perceive color differences between individual pixels, but only between neighborhoods of pixels.
Dithered quantization according to the invention refers to a process of truncating a selected number of bits from a sample, such that only a set of most significant bits remains. The most significant bits, or index bits, are used as an index to the lookup table, but only after the least significant bits of the sample (i.e., the bits that have been truncated) are analyzed to determine whether the most significant bits of the particular sample should be incremented by a value of one. Over a neighborhood of samples, the index bits are incremented at a frequency that approximates linear interpolation. For instance, if a sample falls in a lookup table between adjacent lattice points at a position such that the lattice point having the greater value would be weighted more in conventional linear interpolation, the index bits of a neighborhood of such samples would be incremented by one at a correspondingly high frequency. Thus, although individual quantized samples introduce local errors, the average output data for a neighborhood of samples approximates or converges to the output data that could be obtained using conventional linear interpolation.
The dithered quantization operations of the invention differ from conventional quantization techniques in that the dithered quantization operations of the invention result in output data that approximates the results that could be obtained using conventional linear interpolation and minimizes the overall error for a neighborhood of samples. In contrast, conventional quantization can involve adjusting the value of successive identical samples to an adjacent lattice point, thereby introducing the same local error in each of a neighborhood of samples. It has been noted that this property of conventional quantization introduces artifacts such as contour banding, which is eliminated using the dithered quantization operations of the invention.
One technique for efficiently determining whether the index bits (i.e., the most significant bits) should be incremented by one prior to indexing the lookup table involves use of a mask array that is tiled over the data and has one entry per sample. The least significant bits of the sample are compared with the corresponding entry of the mask array to determine whether the value of the least significant bits (i.e., the bits that have been truncated from the index bits) indicates that the associated index bits are to be incremented. The entries of the mask array are selected and arranged based on the observation that the bits that have been truncated from the index bits are informative of the position of the sample relative to the adjacent lattice points of the lookup table in proportion to the significance of these bits. In other words, the mask array is constructed to give proportionally more weight to the more significant bits and proportionally less weight to the less significant bits when determining how frequently the index bits of a neighborhood of samples should be incremented prior to indexing the lookup table.
Additional features and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by the practice of the invention. The features and advantages of the invention may be realized and obtained by means of the instruments and combinations particularly pointed out in the appended claims. These and other features of the present invention will become more fully apparent from the following description and appended claims, or may be learned by the practice of the invention as set forth hereinafter.